import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.logging.Level;
import java.util.logging.Logger;

public class BloomFilter {
    //位图的长度
    public static final int NUM_SLOTS=1024*1024*8;
    //hash函数的个数，一个hash函数的结果用于标记一个位
    public static final int NUM_HASH=8;
    //位图
    private BigInteger bitmap=new BigInteger("0");

    private int hash(String message,int n){
        message=message+String.valueOf(n);
        try {
            MessageDigest md5=MessageDigest.getInstance("md5");
            byte[] bytes=message.getBytes();
            md5.update(bytes);
            byte[] digest=md5.digest();
            BigInteger bi=new BigInteger(digest);

            return  Math.abs(bi.intValue())%NUM_SLOTS;
        } catch (NoSuchAlgorithmException e) {
            Logger.getLogger(BloomFilter.class.getName()).log(Level.SEVERE,null,e);
        }
        return -1;
    }


    public void addElement(String message){
        for(int i=0;i<NUM_HASH;i++){
            int hashcode=hash(message,i);
            if(!bitmap.testBit(hashcode)){
                bitmap=bitmap.or(new BigInteger("1").shiftLeft(hashcode));
            }
        }
    }

    public boolean check(String message){
        for(int i=0;i<NUM_HASH;i++){
            int hashcode=hash(message,i);
            if(!this.bitmap.testBit(hashcode)){
                return  false;
            }
        }
        return  true;
    }

    public static void main(String[] args) {
        BloomFilter bloomFilter=new BloomFilter();
        ArrayList<String> contents=new ArrayList<>();
        contents.add("124");
        contents.add("2222");
        contents.add("fff");

        for(String str:contents){
            bloomFilter.addElement(str);
        }
        System.out.println(bloomFilter.check("12"));
        System.out.println(bloomFilter.check("fff"));
        System.out.println(bloomFilter.check("2222"));
    }
}
